import java.util.ArrayList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 26727
 * Date: 2024-06-17
 * Time: 10:29
 */
class Solution7 {
    String[] hash = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    List<String> ret;
    StringBuilder path;
    public List<String> letterCombinations(String digits) {
        ret = new ArrayList<>();
        path = new StringBuilder();

        //特殊处理
        if(digits.length() == 0) {
            return ret;
        }

        dfs(digits,0);

        return ret;
    }

    void dfs(String digits, int pos) {
        if(pos == digits.length()) {
            ret.add(path.toString());
            return;
        }
        //当前字符串-->对应字符
        String cur = hash[digits.charAt(pos)-'0'];

        for(int i = 0; i < cur.length(); i++) {
            path.append(cur.charAt(i));
            dfs(digits,pos+1);
            //恢复现场
            path.deleteCharAt(path.length()-1);
        }
    }
}
